package dynamicProgramming;

/**
 * @author zxc
 * @date 2023/02/01 10:49
 **/

import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Set;

/**
 * 题目 ：无重复字符的最长子串
 * 题目详述 ：
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
 *
 * 提示：
 * 0 <= s.length <= 5 * 104
 * s 由英文字母、数字、符号和空格组成
 */
public class LengthOfLongestSubstring {
    /**
     * 思路 ：
     * 假设 f(i)为以第i个字符为结束字符的无重复最长子串长度;
     * ===》
     * （1）即，遍历以第i个字符为结束字符的无重复最长子串（i的取值范围 ：[0,s.length()]）;
     * ===》 上述可以遍历到所有可能的无重复子串;
     * （2）特殊情况 ：字符串s为0/1个字符时，无重复最长子串长度，即为字符串长度;
     *
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();
        int maxLength = Integer.MIN_VALUE;
        // 若是字符串长度为 0/1时，即最长无重复子串长度为 0/1;
        if(len <= 1){
            return len;
        }
        // 遍历以第i个字符为结束字符的最长无重复子串;
        for(int i = 1; i < len; i++){
            // 即，使用Set集合来记录当前子串中元素;（Set集合特点 ：元素不重复）
            Set<Character> set = new HashSet<>();
            // 记录以第i个字符为结束字符的最长无重复子串长度;
            int k = 0;
            // （1）未遍历完字符串s ; （2）当前遍历字符ch，之前还未被遍历过;
            while(i >= k && !set.contains(s.charAt(i - k))){
                set.add(s.charAt(i - k));
                k++;
            }
            // 变量maxLength，来记录长度为n的字符串s中最长无重复子串;
            maxLength = Math.max(maxLength , k);
        }
        return maxLength;
    }
}
